﻿package string;

public class 判断字符串中所有字符是否只出现一次 {

	public static boolean isUnique(char[] chas) {
		boolean[] map = new boolean[256];
		for (int i = 0; i < chas.length; i++) {
			if (map[chas[i]]) {
				return false;
			} else {
				map[chas[i]] = true;
			}
		}
		return true;
	}

	public static boolean isUnique2(char[] chas){
		if(chas==null||chas.length==0) return false;
		heapSort(chas);
		for(int i=1;i<chas.length;i++){
			if(chas[i]==chas[i-1]){
				return false;
			}
		}
		return true;
	}
	public static void heapSort(char[] chas){
		//建立堆
		for(int i=0;i<chas.length;i++)
		{
			heapOne(chas,i);
		}
		//调整堆
		for(int i=chas.length/2;i>=0;i--){
			swap(chas,0,i);
			heapify(chas,0,i);//保证第0号元素最大
		}
	}

	public static void heapify(char[] chas, int i, int size){
		int left = i*2+1;//i结点的左孩子
		int right = i*2+2;//i结点的右孩子
		int largest = i;
		while(left<size){
			if(chas[left]>chas[largest]){
				//如果左孩子比根节点大
				largest = left;
			}
			if(right<size&&chas[right]>chas[largest]){
				largest = right;
			}
			if(largest!=i){
				swap(chas,i,largest);
			}
			i=largest;
			left =i*2+1;
			right = i*2+2;
		}
	}

	/**
	 * 调整堆，如果发现孩子结点的值比根节点的值大，则进行交换
	 * 
	 * @param chas
	 * @param i
	 */
	public static void heapOne(char[] chas, int i) {
		int parent = 0;
		while (i != 0) {
			parent = (i - 1) / 2;
			if (chas[parent] < chas[i]) {
				swap(chas, parent, i);
				i = parent;
			} else {
				break;
			}
		}
	}

	/**
	 * 交换
	 * 
	 * @param chas
	 * @param a
	 * @param b
	 */
	public static void swap(char[] chas, int a, int b) {
		char tmp = chas[a];
		chas[a] = chas[b];
		chas[b] = tmp;
	}

	public static void main(String[] args) {
		System.out.println(isUnique2("abcdefhi".toCharArray()));
		System.out.println(isUnique2("abcdefhia".toCharArray()));
	}

}
